package com.nowcoder.code.hjnc;

public class NC140 {

    public static void main(String[] args) {
        int[] arr = {5, 2, 3, 1, 4};
        new NC140().MySort(arr);
        for (int i : arr) {
            System.out.print(i + ",");
        }

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     *
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    public void quickSort(int[] arr, int start, int end) {

        if (start >= end) {
            return;
        }

        int mid = arr[start];
        int os = start;
        int oe = end;

        while (start < end) {
            while (arr[start] <= mid && start < end) {
                start++;
            }
            while (arr[end] >= mid && start < end) {
                end--;
            }

            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
        }

        if (arr[os] > arr[start]) {
            int tmp = arr[os];
            arr[os] = arr[start];
            arr[start] = tmp;
        }



        quickSort(arr, os, start - 1);
        quickSort(arr, start + 1, oe);


    }

}
